"""Functions for creating various mazes"""

from pyre.core import types, dice
from pyre.gen import cave

def perfect(world, wall=types.ColoredChar('#'), dug=types.ColoredChar('.')):
    """
    perfect(World, ColoredChar, ColoredChar): None
    Creates a perfect maze on the world, meaning that there is exactly one
    path connecting any two points on the map.
    """

    _apply_maze(world, _abstract_perfect, wall, dug)


def braid(world, wall=types.ColoredChar('#'), dug=types.ColoredChar('.')):
    """
    braid(World, ColoredChar, ColoredChar): None
    Creates a braid maze on the world, meaning that the maze has no dead ends
    """

    _apply_maze(world, _abstract_braid, wall, dug)


def half_braid(world, wall=types.ColoredChar('#'), dug=types.ColoredChar('.')):
    """
    half_braid(World, ColoredChar, ColoredChar): None
    Creates a partial braid maze on the world, meaning that there will be some
    dead ends, and but that loops will be present.
    """

    _apply_maze(world, _abstract_half_braid, wall, dug)


def _apply_maze(world, algorithm, wall, dug):
    cols, rows = (world.cols - 1) // 2, (world.rows - 1) // 2

    maze = algorithm(cols, rows)
    cave.fill_rock(world, wall)
    for node in maze:
        # every node is one tile away from the next
        pos = types.Coordinate(node[0] * 2 + 1, node[1] * 2 + 1)
        world.set_tile(pos, dug, True)
        for edge in maze[node]:
            dest = pos + node.direction_to(edge)
            world.set_tile(dest, dug, True)


def medieval(world, wall=types.ColoredChar('#'), dug=types.ColoredChar('.')):
    """
    medieval(World, ColoredChar, ColoredChar): None
    Creates a traditional dungeon map with rooms connected by corridors.
    """

    maze_dim = min(world.cols // 8, world.rows // 8)
    room_dim = world.cols // maze_dim, world.rows // maze_dim
    maze = _abstract_half_braid(maze_dim, maze_dim)

    rooms = {}
    for node in maze:
        # rooms are bigger at least 3x3 and no bigger than 8x8
        pos = types.Coordinate(node[0] * room_dim[0], node[1] * room_dim[1])
        dim = dice.rand_coordinate(3, 3, room_dim[0] - 1, room_dim[1] - 1)
        off_max = room_dim - dim
        off = dice.rand_coordinate(1, 1, off_max[0], off_max[1])
        rooms[node] = pos + off, pos + off + dim

    cave.fill_rock(world, wall)
    for room in rooms.values():
        x1, y1 = room[0]
        x2, y2 = room[1]
        for x in range(x1, x2):
            for y in range(y1, y2):
                world.set_tile((x, y), dug, True)

    for node in maze:
        for edge in maze[node]:
            _connect_rooms(rooms[node], rooms[edge], world, dug)


def _connect_rooms(start, goal, world, dug):
    x1, y1 = dice.rand_coordinate(start[0][0] + 1, start[0][1] + 1,
                                  start[1][0] - 1, start[1][1] - 1)
    x2, y2 = dice.rand_coordinate(goal[0][0] + 1, goal[0][1] + 1,
                                  goal[1][0] - 1, goal[1][1] - 1)

    ix = 1 if x1 < x2 else -1
    iy = 1 if y1 < y2 else -1

    while x1 != x2:
        world.set_tile((x1, y1), dug, True)
        x1 += ix
    while y1 != y2:
        world.set_tile((x1, y1), dug, True)
        y1 += iy


def _abstract_perfect(cols, rows):
    maze = {types.Coordinate(x, y): set()
            for x in range(cols) for y in range(rows)}
    stack = [dice.choice(maze)]
    front = set(maze)
    front.difference_update(stack)

    while len(stack) > 0:
        curr = stack[-1]
        try:
            dig = dice.choice(pos for pos in _adj(maze, curr) if pos in front)
            front.remove(dig)
            stack.append(dig)
            maze[curr].add(dig)
        except IndexError: # no unvisited adjacent for choice
            stack.pop()

    return maze


def _abstract_braid(cols, rows):
    maze = _abstract_perfect(cols, rows)
    _remove_deadends(maze, _find_deadends(maze))
    return maze


def _abstract_half_braid(cols, rows):
    maze = _abstract_perfect(cols, rows)
    deadends = _find_deadends(maze)
    deadends = [deadend for deadend in deadends if dice.coinflip()]
    _remove_deadends(maze, deadends)
    return maze


def _find_deadends(maze):
    # without a bidirectional graph, we'll dead end in open corridors
    _bidirect_edges(maze)

    visited = set()
    stack = [dice.choice(maze)]
    deadends = set()
    while len(stack) > 0:
        node = stack.pop()
        visited.add(node)
        adj = [pos for pos in _adj(maze, node) if
               pos not in visited and pos in maze[node]]
        if len(adj) > 0:
            stack.extend(adj)
        else:
            deadends.add(node)

    # medieval digs a corridor for each each, so we want a directed graph
    _prune_bidirection(maze)

    return deadends


def _remove_deadends(maze, deadends):
    for node in deadends:
        dig = dice.choice(pos for pos in _adj(maze, node)
                          if pos not in maze[node])
        maze[node].add(dig)


def _bidirect_edges(maze):
    for node in maze:
        for edge in maze[node]:
            maze[edge].add(node)


def _prune_bidirection(maze):
    for node in maze:
        for edge in maze[node]:
            if node in maze[edge]:
                maze[edge].remove(node)


def _adj(maze, pos):
    adj = [pos + (0, 1), pos + (0, -1), pos + (1, 0), pos + (-1, 0)]
    return [pos for pos in adj if pos in maze]
